package com.peng.leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * BuildTree2
 * 105. 从前序与中序遍历序列构造二叉树
 * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 * <p>
 * Created on 2022/11/27
 *
 * @author lupeng
 */
public class BuildTree2 {

    private int[] preorder;
    private Map<Integer, Integer> inorderTreeNode2IndexMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            inorderTreeNode2IndexMap.put(inorder[i], i);
        }
        return build(0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
        if (preorderLeft > preorderRight) {
            return null;
        }
        int rootVal = preorder[preorderLeft];
        int inorderRootIndex = inorderTreeNode2IndexMap.get(rootVal);
        int inorderLeftLength = inorderRootIndex - inorderLeft;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorderLeft + 1, preorderLeft + inorderLeftLength,
                inorderLeft, inorderLeft + inorderLeft - 1);
        root.right = build(preorderLeft + inorderLeftLength + 1, preorderRight,
                inorderRootIndex + 1, inorderRight);
        return root;
    }

}
